import java.util.Arrays;

public class HeapList {
    public static void main(String[] args) {
        int[] arr={4,8,9,5,6};
        heapsort(arr);
    }


    public static void heapsort(int[] arr){
        int temp=0;
        for (int i = arr.length/2-1; i >=0 ; i--) {
            heaplist(arr,i,arr.length);
        }

        for (int i = arr.length-1; i >0 ; i--) {
            temp=arr[i];
            arr[i]=arr[0];
            arr[0]=temp;
            heaplist(arr,0,i);
        }
        System.out.println(Arrays.toString(arr));
    }
    public static void heaplist(int[] arr,int i,int length){
        int temp=arr[i];
        for (int j = i*2+1; j < length; j=j*2+1) {
            if (j+1<length&&arr[j]<arr[j+1]){
                j++;
            }
            if (arr[j]>temp){
                arr[i]=arr[j];
                i=j;
            }else {
                break;
            }
        }
        arr[i]=temp;
    }

}
